package 算法;

public class 插入排序 {
    public static void main(String[] args) {
        /*
        插入排序：将 0索引到 N索引的元素看作是有序的，把 N+1索引的元素到最后一个是无序的
        遍历无序的数据，将遍历的元素插入有序序列合适的位置中
        如果遇到相同的数据，插在后面
         */
        int[] arr = {1,36, 12, 6, 3, 9, 55, 94, 33, 152, };
//        1.找到无序的数据是从哪个索引开始的
        int startIndex = -1;//由于-1值在索引中不存在，所以将其当做是默认值
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > arr[i + 1]) {
                startIndex=i+1;
                break;
//                System.out.print(i + " ");//这里表示的是从i索引开始无序
            }
        }
//      2.遍历从startIndex开始到最后一个元素，依次得到无序的数组中的每一个元素
        for (int i = startIndex; i < arr.length; i++) {
                int j=i;
                while(j>0&&arr[j]<arr[j-1]){
                    int temp =arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=temp;
                    j--;
                    System.out.println(arr[j]);
                }
        }
       getPrintArr(arr);

    }
    private static void getPrintArr(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }
}
